package elka.gis.postman.helper.impl;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import elka.gis.postman.bean.Edge;
import elka.gis.postman.bean.Graph;
import elka.gis.postman.bean.Path;
import elka.gis.postman.bean.Vertex;
import elka.gis.postman.helper.DijkstraSearcher;

/**
 * Klasa pozwala na uzupelnienie grafu o krawedzie na podstawie algorytmu dijkstry aby ten byl spojny
 * @author Wojtek
 *
 */
public class DijkstraSearcherImpl implements DijkstraSearcher {
	
	/**
	 * Dodaje krawedzie do grafu aby byl spojny
	 */
	public Graph addEdgesToOddVertices( Graph graph) {
		Graph resultGraph = graph.copy();
		List<Path> missingPaths = findMissingPaths(resultGraph.getAllVertexOddDegree(), resultGraph);
		for(Path p :missingPaths){
			List<Edge> edges = p.getEdges();
			for(Edge e:edges){
				e.getStartPoint().addEdge(e);
				e.getEndPoint().addEdge(e);
				resultGraph.getEdges().add(e);
			}
			
		}
		
		
		return resultGraph;
	}
	
	/**
	 * Wyszukuje sciezki ktore trzeba dodac do grafu
	 * @param oddVertices
	 * @param graph
	 * @return
	 */
	private List<Path> findMissingPaths(List<Vertex> oddVertices, Graph graph) {
		List<Path> paths = new ArrayList<Path>();
		
		while(!oddVertices.isEmpty()){
			paths.add(findShortestPath(oddVertices.remove(0),oddVertices,graph));
		}
		
		
		return paths;
	}

	/**
	 * Wyszukiwanie najkrotszej scieszki za pomoca algorytmu dijkstry
	 * @param startVertex
	 * @param sourceVertex
	 * @param graph
	 * @return
	 */
	private Path findShortestPath(Vertex startVertex, List<Vertex> sourceVertex, Graph graph){
		Set<Integer> visitedVertices = new HashSet<Integer>();
		Map<Integer,Distance> distances = initDistances(graph, startVertex);

		List<Vertex> tempSourceVertices = new ArrayList<Vertex>(sourceVertex);
		Vertex actualVertex = startVertex;
		while(!tempSourceVertices.isEmpty() && actualVertex!=null){
			visitedVertices.add(actualVertex.getId());
			actualizeDistances(distances, actualVertex);
			actualVertex =  chooseNextVertex(visitedVertices, distances);
			tempSourceVertices.remove(actualVertex);
		}
		
		Vertex choosen = chooseVertexWithShortestPath(distances,sourceVertex);
		sourceVertex.remove(choosen);
		return createPath(startVertex,choosen,distances);
	}
	
	private Map<Integer,Distance> initDistances(Graph graph, Vertex startVertex){
		Map<Integer, Distance> distances = new HashMap<Integer, Distance>();
		for(Vertex v :graph.getVertices()){
			if(!v.equals(startVertex)){
				distances.put(v.getId(), new Distance(v));
			}else{
				distances.put(v.getId(), new Distance(v,0));
			}
		}
		return distances;
	}

	private void actualizeDistances(Map<Integer,Distance> distances,Vertex actualVertex){
		int actualDistance = distances.get(actualVertex.getId()).distance;
		for(Edge e:actualVertex.getEdges()){
			Vertex targetVertex = chooseTargetVertex(e,actualVertex);
			if(actualDistance + e.getLength() < distances.get(targetVertex.getId()).distance){
				distances.get(targetVertex.getId()).distance = actualDistance + e.getLength();
			}
		}
	}
	
	private Vertex chooseNextVertex(Set<Integer> visited, Map<Integer, Distance> distances){
		int minDistance = Integer.MAX_VALUE;
		Vertex nextVertex = null;
		for(int id : distances.keySet()){
			if(distances.get(id).distance <= minDistance && !visited.contains(id)){
				minDistance = distances.get(id).distance;
				nextVertex = distances.get(id).v;
			}
		}
		return nextVertex;
	}
	
	private Vertex chooseVertexWithShortestPath(
			Map<Integer, Distance> distances, List<Vertex> sourceVertex) {
		int minDistance = Integer.MAX_VALUE;
		Vertex nextVertex = null;
		for(Vertex v: sourceVertex){
			Distance d = distances.get(v.getId());
			if(d.distance < minDistance){
				minDistance = d.distance;
				nextVertex = d.v;
			}
		}
		
		
		return nextVertex;
	}
	
	private Vertex chooseTargetVertex(Edge e,Vertex actualVertex){
		if(e.getStartPoint().equals(actualVertex)){
			return e.getEndPoint();
		}else{
			return e.getStartPoint();
		}
	}
	
	
	private Path createPath(Vertex startVertex, Vertex choosen, Map<Integer, Distance> distances) {
		Vertex actualVertex = choosen;
		List<Edge> edges = new ArrayList<Edge>();
		Path p = new Path();
		p.setEdges(edges);
		while(!startVertex.equals(actualVertex)){
			for(Edge e :actualVertex.getEdges()){
				Vertex targetVertex = chooseTargetVertex(e,actualVertex);
				if(distances.get(actualVertex.getId()).distance -distances.get(targetVertex.getId()).distance == e.getLength()){
					edges.add(0, e);
					actualVertex = targetVertex;
					break;
				}
				
			}
			
		}
		
		
		return p;
	}
	
	private class Distance {
		
		private Vertex v;
		
		private int distance;
		
		public Distance(Vertex v){
			this.v= v;
			distance = Integer.MAX_VALUE;
		}
		public Distance(Vertex v, int distance){
			this.v=v;
			this.distance = distance;
		}
		
	}


	

}
